﻿#include <stdio.h>

int subarraysWithKDistinct(int* A, int ASize, int K) {
	if (K == 0 || !A || ASize == 0)
		return 0;
	// 統計最多K的所有子數組(因為A(i)<=ASize,故而需要分配ASize + 1內存區域)
	int* mapKMost = malloc(sizeof(int) * (ASize + 1));
	memset(mapKMost, 0, sizeof(int) * (ASize + 1));
	int sizeKMost = 0;
	// 統計最多(k-1)的所有子數組
	int* mapLessK = malloc(sizeof(int) * (ASize + 1));
	memset(mapLessK, 0, sizeof(int) * (ASize + 1));
	int sizeLessK = 0;
	int leftKMost = 0;
	int leftLessK = 0;
	int right = 0;
	int ans = 0;
	while (right < ASize) {
		// add to both map
		const int numR = A[right];
		if (mapKMost[numR] == 0)
		{
			sizeKMost++;
		}
		mapKMost[numR]++;
		if (mapLessK[numR] == 0)
		{
			sizeLessK++;
		}
		mapLessK[numR]++;
		// deal if size is above the limit k
		while (sizeKMost > K) {
			const int num = A[leftKMost];
			mapKMost[num]--;
			if (mapKMost[num] == 0)
				sizeKMost--;
			leftKMost++;
		}
		// deal if size is above the limit k-1
		while (sizeLessK > K - 1) {
			const int num = A[leftLessK];
			mapLessK[num]--;
			if (mapLessK[num] == 0)
				sizeLessK--;
			leftLessK++;
		}
		// (right-leftKMost+1)+(right-leftLessK+1) => leftLessK - leftKMost
		ans += leftLessK - leftKMost;
		// right pointer add
		right++;
	}
	// release memonery
	free(mapKMost);
	mapKMost = NULL;
	free(mapLessK);
	mapLessK = NULL;
	return ans;
}

int main()
{
	int num[] = { 1, 2, 1, 2, 3 };
	printf("\nwant:7, ans = %d", subarraysWithKDistinct(num, 5, 2));

	int num1[] = { 1, 2, 1, 3, 4 };
	printf("\nwant:3, ans = %d", subarraysWithKDistinct(num1, 5, 3));

	int num2[] = { 2, 2, 3, 3, 3, 1, 3 };
	printf("\nwant:13, ans = %d", subarraysWithKDistinct(num2, 7, 2));

	int num3[] = { 2, 1, 1, 1, 2 };
	printf("\nwant:8, ans = %d", subarraysWithKDistinct(num3, 5, 1));

	int num4[] = { 1, 2 };
	printf("\nwant:8, ans = %d", subarraysWithKDistinct(num4, 2, 1));

	return 0;
}